#include <string.h> // for strtok();
#include <stdio.h> // for fopen();
#include <errno.h> // for strerror();
#include <stdlib.h> // for exit();

//#define DEBUG
#define HASHTABLE_SLOTS 10

typedef struct node{
	int pid;
	char *cmd;
	int flag;
	struct node *next;
} htable_entry;

/* These head nodes don't store any entries but just heads 
 *
 * Hash table slots design:
 * head[0] -> [pid|cmd|flag] -> [pid|cmd|flag] -> NULL
 * head[1] -> [pid|cmd|flag] -> [pid|cmd|flag] -> [pid|cmd|flag] -> NULL
 * ...
 * ...
 * head[HASHTABLE_SLOTS] -> [pid|cmd|flag] -> [pid|cmd|flag] -> [pid|cmd|flag] -> NULL
 *
 */
htable_entry head_node[HASHTABLE_SLOTS];

#ifdef DEBUG
void print_hash_table()
{
	int i;
	htable_entry *current;
	printf("========== Hash table ==========\n");
	for(i = 0; i < HASHTABLE_SLOTS; i++) {
		printf("row-%d ", i);
		current = &head_node[i];
		while (current->next != NULL) {
			printf("%d->(%s) ", current->next->pid, current->next->cmd);
			current=current->next;
		}
		printf("\n\n");
	}
	printf("========================\n");
}
#endif

htable_entry *get_filled_new_node(int pid, char*cmd)
{
	htable_entry *tmp_node;

	tmp_node = malloc(sizeof(htable_entry));
	tmp_node->pid = pid;
	tmp_node->cmd = malloc(strlen(cmd));
	strcpy(tmp_node->cmd, cmd);
	tmp_node->flag = 1;
}

/* build_hash_table() sets flag of each hashtable entry to 1
 *
 * and reset_all_htable_entry_flags() resets it to zero after every time
 * we run "ps -e" so new process entries in the hashtable are marked as 1 
 * and vanished process entries are marked as 0
 *
 */	
int build_hash_table(int pid, char *cmd)
{
	/* Hashing function */
	int slot_number = pid%HASHTABLE_SLOTS;

	htable_entry *current;
	htable_entry *tmp_node;

	current = &head_node[slot_number];
	/* if the slot is empty then just insert the process entry at the beginning */
	if (current->next == NULL) {
		tmp_node = get_filled_new_node(pid, cmd);
		tmp_node->next = NULL;
		current->next=tmp_node;
	} else {
		while(current->next != NULL && current->next->pid < pid) {
			current = current->next;
		}
		/* we don't create duplicate entries for pid in the hash table
 		 * just replace the cmd name and mark the flag to 2 so that it 
 		 * does not come in our new and vanished processes list 
 		 */
		if(current->next && current->next->pid == pid) {
			strcpy(current->next->cmd, cmd);
			current->next->flag = 2;
		/* Insert the node before the node with greater pid than it
 		 */
		} else {
			tmp_node = get_filled_new_node(pid, cmd);
			tmp_node->next = current->next;
			current->next = tmp_node;
		}
	}
}

/* Just set ->next field of each head to NULL */
void initialize_htable_heads()
{
	int i;
	for(i = 0; i < HASHTABLE_SLOTS; i++)
		head_node[i].next = NULL;
}

void reset_all_htable_entry_flags()
{
	int i;
	htable_entry *current;
	for(i = 0; i < HASHTABLE_SLOTS; i++) {
		current = &head_node[i];
		while (current->next != NULL) {
			current->next->flag = 0;
			current=current->next;
		}
	}
}
void parse_line(char *ps_output)
{
	char *pid;
	char *cmd;
	char *temp;

	//printf("line: %s\n", ps_output);
	
	/* remove the leading white spaces*/
	/* can not increment ps_output as there will be memory leak */
	temp = ps_output;
	while(isspace(*temp)) temp++;
	if (*temp == 0)
		return;

	/* remove trailing \n from line */
	*(temp+(strlen(temp)-1)) = '\0';

	pid = strsep(&temp, ",");
	if(atoi(pid) == 0)
		return;
	//printf("pid: %d ", atoi(pid));
	cmd = temp;
	//printf("cmd: %s\n", cmd);
	
	build_hash_table(atoi(pid), cmd);
}

find_new_and_vanished_processes()
{
	int i;
	htable_entry *current;
	htable_entry *temp;
	for(i = 0; i < HASHTABLE_SLOTS; i++) {
		current = &head_node[i];
		while (current->next != NULL) {
			if(current->next->flag == 0) {
				printf("%d(%s) has vanished\n", 
					current->next->pid, current->next->cmd);
				/* flag 0 means process has exited so remove it 
 				 * from the hash table and free its memory
 				 */
					temp = current->next;
					current->next = current->next->next;
					free(temp);
			/* flag 1 means its a new process
 			 */
			} else if (current->next->flag == 1) {
				printf("%d(%s) is new\n", 
					current->next->pid, current->next->cmd);
				current=current->next;
			} else {
				current=current->next;
			}
		}
	}
}

int main()
{
	FILE *fp;
	char *ps_output = (char *) malloc(100);
	int first = 1;

	initialize_htable_heads();
	while(1) {
		system("ps -eo \"%p,%c\" > .tmp_ps");

		fp = fopen(".tmp_ps", "r");
		if (fp == NULL) {
			printf("Error: cannnot open .tmp_ps file. Error: %s\n",
				strerror(errno));
			exit(1);
		}
		
		while (fgets(ps_output, 100, fp) != NULL) {
			/* parse_line also builds hash table for all output
			 * and sets flags of all processes to 1
			 */
			parse_line(ps_output);
		}
		if(!first)
			find_new_and_vanished_processes();
#ifdef DEBUG
		print_hash_table();
#endif
		first = 0;
		reset_all_htable_entry_flags();
		fclose(fp);
		sleep(10);
	}
	free(ps_output);
}
